package com.demo.java.OD601_650.OD648;

import java.util.Scanner;
import java.util.Arrays;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【最多组合直角三角形个数(A卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/147036664
 */
public class OdMain {
    public static void main(String[] args) {
        // 处理输入
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();  // 读取测试用例数
        for (int i = 0; i < T; i++) {
            int N = in.nextInt();  // 读取线段数量
            int[] nums = new int[N];  // 存储每条线段的长度
            for (int j = 0; j < N; j++) {
                nums[j] = in.nextInt();  // 读取线段长度
            }

            Arrays.sort(nums);  // 对线段数组进行排序
            System.out.println(dfs(nums, 0));  // 调用DFS函数，查找并输出最多可以组成的直角三角形数量
        }
    }

    // 深度优先搜索函数，查找所有可能的直角三角形组合
    public static int dfs(int[] lines, int index) {
        int maxVal = 0;  // 当前找到的最大直角三角形数量
        int a, b, c;

        // 遍历所有三条线段组合
        for (int i = index; i < lines.length - 2; i++) {
            a = lines[i];
            if (a == 0) {
                continue;  // 已使用的线段跳过
            }
            for (int j = i + 1; j < lines.length - 1; j++) {
                b = lines[j];
                if (b == 0) {
                    continue;
                }
                for (int k = j + 1; k < lines.length; k++) {
                    c = lines[k];
                    if (c == 0) {
                        continue;
                    }
                    // 判断是否满足勾股定理
                    if ((a * a + b * b) == c * c) {
                        lines[i] = 0;  // 标记线段已使用
                        lines[j] = 0;
                        lines[k] = 0;
                        maxVal = Math.max(maxVal, dfs(lines, i + 1) + 1);  // 递归查找下一个三角形
                        lines[i] = a;  // 恢复线段状态
                        lines[j] = b;
                        lines[k] = c;
                    }
                }
            }
        }

        return maxVal;  // 返回最多可组成的直角三角形数
    }
}